package main

import (
	"bufio"
	"encoding/json"
	"fmt"
	"log"
	"math"
	"net"
	"os"
	"runtime"
	"strconv"
	"strings"
	"sync"
	"time"
)

//文件路径
var filePath = "out.txt"

// 文件资源
var fileResource *os.File

//缓冲区
var fileBuf *bufio.Reader

// 协程等待
var wg sync.WaitGroup

func main() {

	var startTime = time.Now()

	var err error

	fileResource, err = os.Open(filePath)

	if err != nil {
		log.Fatalln(err)
	}
	//建立缓冲区，把文件内容放到缓冲区中
	fileBuf = bufio.NewReader(fileResource)

	ips = make(map[uint8]*ipInfo)

	//for i := 0; i < 256; i++ {
	//	ips[uint8(i)] = &ipInfo{
	//		Ch:       map[uint8]*ipInfo{},
	//		Children: map[uint8][]ipInfo{},
	//	}
	//}
	//runtime.GOMAXPROCS(runtime.NumCPU())
	cpus := runtime.NumCPU() * 2
	for i := 0; i < cpus; i++ {
		wg.Add(1)
		go handle(i)
	}
	wg.Wait()
	fmt.Println("一级处理完成")
	fmt.Println("开始二级处理")

	for _k, _ips := range ips {
		wg.Add(1)
		go handle16(_k, _ips)
	}
	wg.Wait()

	_ = fileResource.Close()

	fmt.Println("数据处理结束，准备导出到文件")
	fmt.Println("开始输出新规则")
	f, err := os.Create(filePath + ".new.txt") //创建文件
	if err != nil {
		log.Fatal(err)
	}
	defer f.Close()
	w := bufio.NewWriter(f)
	for _, v := range ips {
		WriteIps(v, w)
	}
	_ = w.Flush()

	fmt.Println("开始输出废弃规则")
	f2, err := os.Create(filePath + ".del.json") //创建文件
	if err != nil {
		log.Fatal(err)
	}
	defer f2.Close()
	w2 := bufio.NewWriter(f2)
	f2buf, err := json.Marshal(ids)
	if err != nil {
		log.Fatal(err)
	}

	_, err = w2.Write(f2buf)
	if err != nil {
		log.Fatal(err)
	}
	_ = w2.Flush()

	endTime := time.Now()
	fmt.Println("程序开始时间", startTime)
	fmt.Println("程序结束时间", endTime)
	fmt.Println("程序耗时", endTime.Sub(startTime))

}

func WriteIps(_ips *ipInfo, w *bufio.Writer) {

	if _ips.Index > 0 {
		// 写当前
		_, err := w.WriteString(_ips.Line)
		if err != nil {
			log.Fatal(err)
		}
	} else {
		// 写子代
		for _, v := range _ips.Ch {
			WriteIps(v, w)
		}
	}

}

func handle(i int) {
	defer wg.Done()
	for {
		fmt.Printf("协程 %d 准备读取新数据\n", i)
		line, lineNumber, err := readLine(i)
		if err != nil {
			log.Printf("协程 %d 退出", i)
			break
		}
		mIpS(i, line, lineNumber)
	}

}

//9-16
func handle16(_k uint8, _ips *ipInfo) {
	defer wg.Done()
	if _ips.Index != 0 {
		// 清理掉数据
		_ips.Children = make(map[uint8][]ipInfo)
		fmt.Printf("二级 %d.0.0.0/%d 处理完毕 \n", _k, _ips.Mask)
		return
	}
	for _k2, v := range _ips.Children {
		wg.Add(1)
		fmt.Printf("二级 %d.%d.0.0 开始处理 \n", _k, _k2)
		mIpS16(_k, v, _ips)
		fmt.Printf("二级 %d.%d.0.0 处理完毕 \n", _k, _k2)
	}

}

// 17-24
func handle24(_k, _k2 uint8, _ips *ipInfo) {
	defer wg.Done()
	if _ips.Index != 0 {
		// 清理掉数据
		_ips.Children = make(map[uint8][]ipInfo)
		fmt.Printf("三级 %d.%d.0.0/%d 处理完毕 \n", _k, _k2, _ips.Mask)
		return
	}
	for _k3, v := range _ips.Children {
		wg.Add(1)
		fmt.Printf("三级 %d.%d.%d.0 开始处理 \n", _k, _k2, _k3)
		mIpS24(_k, _k2, v, _ips)
		fmt.Printf("三级 %d.%d.%d.0 处理完毕 \n", _k, _k2, _k3)
	}

}

// 25-32
func handle32(_k, _k2, _k3 uint8, _ips *ipInfo) {
	defer wg.Done()
	if _ips.Index != 0 {
		// 清理掉数据
		_ips.Children = make(map[uint8][]ipInfo)
		fmt.Printf("二级 %d.%d.%d.0/%d 处理完毕 \n", _k, _k2, _k3, _ips.Mask)
		return
	}
	for _k4, v := range _ips.Children {
		fmt.Printf("二级 %d.%d.%d.%d/%d 开始处理 \n", _k, _k2, _k3, _k4, _ips.Mask)
		mIpS32(v, _ips)
		fmt.Printf("二级 %d.%d.%d.%d/%d 处理完毕 \n", _k, _k2, _k3, _k4, _ips.Mask)
	}

}

// 第二次处理 异步 X.X.0.0 256 进行比对
func mIpS16(_k uint8, _ips []ipInfo, _mips *ipInfo) {
	defer wg.Done()
	for _, v := range _ips {
		// 如果大于 16 进行分流
		if 16 < v.Mask {
			ip := uint8(v.Ip >> 16) // 256 = 1 << 8
			_ip := _mips.Ch[ip]

			if _ip == nil {
				_ip = &ipInfo{
					Children: map[uint8][]ipInfo{},
					Ch:       map[uint8]*ipInfo{},
				}
				_mips.Ch[ip] = _ip
			}

			if _ip.Index > 0 {
				// 匹配到根，当前ip被放弃
				go addDelIpLine(v.Index, v.Line, _ip.Index, _ip.Line)
			} else {
				// 根没有被占用 写入数组数据
				if _ip.Children == nil {
					_ip.Children = make(map[uint8][]ipInfo)
				}
				_ip.Children[0] = append(_ip.Children[0], ipInfo{
					Ip:       v.Ip,
					Mask:     v.Mask,
					Line:     v.Line,
					Index:    v.Index,
					Children: map[uint8][]ipInfo{},
					Ch:       map[uint8]*ipInfo{},
				})
			}

		} else {

			// 是否处理了
			ov := false
			//需要和同级别的所有的选项进行对比 以双方最小的mask为参考
			for _, tV := range _mips.Ch {

				if tV.Index == 0 {
					// 为0的表示没有当前主级 ，只有 children 子级
					continue
				}

				// 测试冲突
				tMask := 32 - uint8(math.Min(float64(tV.Mask), float64(v.Mask)))

				if tV.Ip>>tMask == v.Ip>>tMask {
					// 有匹配项
					if tV.Mask > v.Mask {
						// 等于 新的替换旧的
						go addDelIpLine(tV.Index, tV.Line, v.Index, v.Line)
						tV.Ip = v.Ip
						tV.Mask = v.Mask
						tV.Index = v.Index
						tV.Line = v.Line
					} else {
						// 保持不变 废弃新的
						go addDelIpLine(v.Index, v.Line, tV.Index, tV.Line)
					}
					ov = true
					break
				}
			}

			if !ov {
				// 没有匹配项，继续走吧
				// 小于等于 16
				ip := uint8(v.Ip >> 16)

				_ips := _mips.Ch[ip]
				if _ips == nil {
					_ips = &ipInfo{
						Children: map[uint8][]ipInfo{},
						Ch:       map[uint8]*ipInfo{},
					}
					_mips.Ch[ip] = _ips
				}

				// 新增新的 没有旧的
				_ips.Ip = v.Ip
				_ips.Mask = v.Mask
				_ips.Line = v.Line
				_ips.Index = v.Index
				go addDelIpLines(_ips.Children, v.Index, v.Line)
				// 回收内存
				_ips.Children = nil
			}
		}
	}

	for _k2, _ips := range _mips.Ch {
		wg.Add(1)
		go handle24(_k, _k2, _ips)
	}

}

// 第二次处理 异步 X.X.0.0 256 进行比对
func mIpS24(_k, _k2 uint8, _ips []ipInfo, _mips *ipInfo) {
	defer wg.Done()
	for _, v := range _ips {
		// 如果大于 16 进行分流
		if 24 < v.Mask {
			ip := uint8(v.Ip >> 8)

			_ip := _mips.Ch[ip]
			if _ip == nil {
				_ip = &ipInfo{
					Children: map[uint8][]ipInfo{},
					Ch:       map[uint8]*ipInfo{},
				}
				_mips.Ch[ip] = _ip
			}
			if _ip.Index > 0 {
				// 匹配到根，当前ip被放弃
				go addDelIpLine(v.Index, v.Line, _ip.Index, _ip.Line)
			} else {
				// 根没有被占用 写入数组数据
				if _ip.Children == nil {
					_ip.Children = make(map[uint8][]ipInfo)
				}
				_ip.Children[0] = append(_ip.Children[0], ipInfo{
					Ip:       v.Ip,
					Mask:     v.Mask,
					Line:     v.Line,
					Index:    v.Index,
					Children: map[uint8][]ipInfo{},
					Ch:       map[uint8]*ipInfo{},
				})
			}

		} else {
			// 是否处理了
			ov := false
			//需要和同级别的所有的选项进行对比 以双方最小的mask为参考
			for _, tV := range _mips.Ch {

				if tV.Index == 0 {
					// 为0的表示没有当前主级 ，只有 children 子级
					continue
				}

				// 测试冲突
				tMask := 32 - uint8(math.Min(float64(tV.Mask), float64(v.Mask)))

				if tV.Ip>>tMask == v.Ip>>tMask {
					// 有匹配项
					if tV.Mask > v.Mask {
						// 等于 新的替换旧的
						go addDelIpLine(tV.Index, tV.Line, v.Index, v.Line)
						tV.Ip = v.Ip
						tV.Mask = v.Mask
						tV.Index = v.Index
						tV.Line = v.Line
					} else {
						// 保持不变 废弃新的
						go addDelIpLine(v.Index, v.Line, tV.Index, tV.Line)
					}
					ov = true
					break
				}
			}

			if !ov {
				// 没有匹配项，继续走吧
				// 小于等于 16
				ip := uint8(v.Ip >> 8)

				_ips := _mips.Ch[ip]
				if _ips == nil {
					_ips = &ipInfo{
						Children: map[uint8][]ipInfo{},
						Ch:       map[uint8]*ipInfo{},
					}
					_mips.Ch[ip] = _ips
				}

				// 新增新的 没有旧的
				_ips.Ip = v.Ip
				_ips.Mask = v.Mask
				_ips.Line = v.Line
				_ips.Index = v.Index
				go addDelIpLines(_ips.Children, v.Index, v.Line)
				// 回收内存
				_ips.Children = nil
			}
		}
	}

	for _k3, _ips := range _mips.Ch {
		wg.Add(1)
		go handle32(_k, _k2, _k3, _ips)
	}
}

// 第二次处理 异步 X.X.0.0 256 进行比对
func mIpS32(_ips []ipInfo, _mips *ipInfo) {
	for _, v := range _ips {

		// 是否处理了
		ov := false
		//todo 需要和同级别的所有的选项进行对比 以双方最小的mask为参考
		for _, tV := range _mips.Ch {

			if tV.Index == 0 {
				// 为0的表示没有当前主级 ，只有 children 子级
				continue
			}

			// 测试冲突
			tMask := 32 - uint8(math.Min(float64(tV.Mask), float64(v.Mask)))

			if tV.Ip>>tMask == v.Ip>>tMask {
				// 有匹配项
				if tV.Mask > v.Mask {
					// 等于 新的替换旧的
					go addDelIpLine(tV.Index, tV.Line, v.Index, v.Line)
					tV.Ip = v.Ip
					tV.Mask = v.Mask
					tV.Index = v.Index
					tV.Line = v.Line
				} else {
					// 保持不变 废弃新的
					go addDelIpLine(v.Index, v.Line, tV.Index, tV.Line)
				}
				ov = true
				break
			}
		}

		if !ov {
			// 没有匹配项，继续走吧
			// 小于等于 16
			ip := uint8(v.Ip)

			_ips := _mips.Ch[ip]
			if _ips == nil {
				_ips = &ipInfo{
					Children: map[uint8][]ipInfo{},
					Ch:       map[uint8]*ipInfo{},
				}
				_mips.Ch[ip] = _ips
			}

			// 新增新的 没有旧的
			_ips.Ip = v.Ip
			_ips.Mask = v.Mask
			_ips.Line = v.Line
			_ips.Index = v.Index
			go addDelIpLines(_ips.Children, v.Index, v.Line)
			// 回收内存
			_ips.Children = nil
		}
	}

}

//单条记录 ip 信息 及后代信息
type ipInfo struct {
	Ip       uint32             // 用于对比的ip
	Mask     uint8              // 用于辅助对比的 掩码
	Line     string             //原字符串
	Index    uint32             // 原文件行号
	Children map[uint8][]ipInfo // 后代非匹配，匹配的废弃了
	Ch       map[uint8]*ipInfo  // 后代非匹配 9-16 17-24 25-32
}

// 被删除的数据复盘信息
type ipInfoDel struct {
	Index1 uint32
	Line1  string
	Index2 uint32
	Line2  string
}

//保留的数据
var ips map[uint8]*ipInfo

// 被删除的数据
var ids []ipInfoDel

// ips 读写锁
var ipsLock sync.Mutex

// 第一次处理 单步进行比对
func mIpS(i int, line string, lineNumber uint32) {
	// 切割字符串
	_ipInfo := strings.Split(line, "|")
	//获取 ip 地址信息 转int
	ipAddress := uint32(ip2Int(_ipInfo[0]))
	// 掩码字符串转int
	maskInt, err := strconv.Atoi(_ipInfo[3])
	if err != nil {
		maskInt = 0
	}
	// 转换为 uin8
	mask := uint8(maskInt)

	ipsLock.Lock()
	defer ipsLock.Unlock()
	fmt.Printf("协程 %d 开始匹配 第 %d 行\n", i, lineNumber)

	// 如果大于8 进行分流
	if 8 < mask {

		ip := uint8(ipAddress >> 24) //右移24位 剩余首位 0-255
		_ip := ips[ip]
		if _ip == nil {
			_ip = &ipInfo{
				Children: map[uint8][]ipInfo{},
				Ch:       map[uint8]*ipInfo{},
			}
			ips[ip] = _ip
		}

		if _ip.Index > 0 {
			// 匹配到根，当前ip被放弃
			go addDelIpLine(lineNumber, line, _ip.Index, _ip.Line)
		} else {
			// 根没有被占用 写入数组数据
			if _ip.Children == nil {
				_ip.Children = make(map[uint8][]ipInfo)
			}
			_ip.Children[0] = append(_ip.Children[0], ipInfo{
				Ip:       ipAddress,
				Mask:     mask,
				Line:     line,
				Index:    lineNumber,
				Children: map[uint8][]ipInfo{},
				Ch:       map[uint8]*ipInfo{},
			})
		}

	} else {
		// 这里是定义为 mask 的根了，所有的 children 都要被放弃了
		// todo 改为遍历
		//ip := uint8(ipAddress >> 24)
		//_ips := ips[ip]
		//if _ips == nil {
		//	_ips = &ipInfo{
		//		Children: map[uint8][]ipInfo{},
		//		Ch:       map[uint8]*ipInfo{},
		//	}
		//	ips[ip] = _ips
		//}
		//
		//if _ips.Index > 0 {
		//
		//	if _ips.Mask < mask {
		//		// 保持不变 废弃新的
		//		go addDelIpLine(lineNumber, line, _ips.Index, _ips.Line)
		//	} else {
		//		// 废弃旧的，变成新的
		//		go addDelIpLine(_ips.Index, _ips.Line, lineNumber, line)
		//		_ips.Ip = ipAddress
		//		_ips.Mask = mask
		//		_ips.Line = line
		//		_ips.Index = lineNumber
		//	}
		//
		//} else {
		//	// 新增新的 没有旧的
		//	_ips.Ip = ipAddress
		//	_ips.Mask = mask
		//	_ips.Line = line
		//	_ips.Index = lineNumber
		//	go addDelIpLines(_ips.Children, lineNumber, line)
		//	// 回收内存
		//	_ips.Children = nil
		//}

		// 是否处理了
		ov := false
		//需要和同级别的所有的选项进行对比 以双方最小的mask为参考
		for _, tV := range ips {

			if tV.Index == 0 {
				// 为0的表示没有当前主级 ，只有 children 子级
				continue
			}

			// 测试冲突
			tMask := 32 - uint8(math.Min(float64(tV.Mask), float64(mask)))

			if tV.Ip>>tMask == ipAddress>>tMask {
				// 有匹配项
				if tV.Mask > mask {
					// 等于 新的替换旧的
					go addDelIpLine(tV.Index, tV.Line, lineNumber, line)
					tV.Ip = ipAddress
					tV.Mask = mask
					tV.Index = lineNumber
					tV.Line = line
				} else {
					// 保持不变 废弃新的
					go addDelIpLine(lineNumber, line, tV.Index, tV.Line)
				}
				ov = true
				break
			}
		}

		if !ov {
			// 没有匹配项，继续走吧
			// 小于等于 16
			ip := uint8(ipAddress >> 24)

			_ips := ips[ip]
			if _ips == nil {
				_ips = &ipInfo{
					Children: map[uint8][]ipInfo{},
					Ch:       map[uint8]*ipInfo{},
				}
				ips[ip] = _ips
			}

			// 新增新的 没有旧的
			_ips.Ip = ipAddress
			_ips.Mask = mask
			_ips.Line = line
			_ips.Index = lineNumber
			go addDelIpLines(_ips.Children, lineNumber, line)
			// 回收内存
			_ips.Children = nil
		}
	}
	fmt.Printf("协程 %d 第 %d 行，已加入列表\n", i, lineNumber)
}

// ips 读写锁
var ipDelLock sync.Mutex

func addDelIpLine(index uint32, line string, index2 uint32, line2 string) {
	if index == index2 {
		// 除了自己
		return
	}
	if index2 == 0 {
		panic("异常数据")
	}
	ipDelLock.Lock()
	defer ipDelLock.Unlock()
	fmt.Printf("%d 行被 %d 行替换 \n", index, index2)
	ids = append(ids, ipInfoDel{
		Index1: index,
		Index2: index2,
		Line1:  line,
		Line2:  line2,
	})
}
func addDelIpLines(_ips map[uint8][]ipInfo, index uint32, line string) {

	for _, v := range _ips {

		var _ip ipInfo
		for _, _ip = range v {
			addDelIpLine(_ip.Index, _ip.Line, index, line)
			if _ip.Children != nil {
				go addDelIpLines(_ip.Children, index, line)
				// 回收内存
				_ip.Children = nil
			}
		}

	}

}

var fileBufReadLock sync.Mutex
var readLineCount uint32 = 0

func readLine(i int) (string, uint32, error) {
	// 开启读锁
	fileBufReadLock.Lock()
	// 解锁
	defer fileBufReadLock.Unlock()
	readLineCount++
	fmt.Printf("协程 %d 读取第 %d 行\n", i, readLineCount)
	//遇到\n结束读取
	b, errR := fileBuf.ReadBytes('\n')
	if errR != nil {
		log.Printf("协程 %d 遇到错误或读取完成，退出\n", i)
		return string(b), readLineCount, errR
	}

	return string(b), readLineCount, errR
}

// Convert uint to net.IP http://www.sharejs.com
func int2Ip(ipnr int64) net.IP {
	var bytes [4]byte
	bytes[0] = byte(ipnr & 0xFF)
	bytes[1] = byte((ipnr >> 8) & 0xFF)
	bytes[2] = byte((ipnr >> 16) & 0xFF)
	bytes[3] = byte((ipnr >> 24) & 0xFF)

	return net.IPv4(bytes[3], bytes[2], bytes[1], bytes[0])
}

// Convert net.IP to int64 ,  http://www.sharejs.com
func ip2Int(ipnr string) int64 {
	bits := strings.Split(ipnr, ".")

	b0, _ := strconv.Atoi(bits[0])
	b1, _ := strconv.Atoi(bits[1])
	b2, _ := strconv.Atoi(bits[2])
	b3, _ := strconv.Atoi(bits[3])

	var sum int64

	sum += int64(b0) << 24
	sum += int64(b1) << 16
	sum += int64(b2) << 8
	sum += int64(b3)

	return sum
}
